package com.example.demo.sort.impl;

import com.example.demo.sort.Sort;
import org.springframework.stereotype.Service;

/**
 * 插入排序
 */
@Service
public class InsertionSort implements Sort {

    @Override
    public String getName() {
        return "插入排序";
    }

    @Override
    public int[] sortArray(int[] nums) {
        int t;
        for (int i = 1; i < nums.length; i++) {
            //先将待处理元素保存到临时变量
            t = nums[i];
            //从i的前一个元素开始往前找
            for (int j = i - 1; j >= 0; j--) {
                if (nums[j] > t) {
                    //元素比t大，后移
                    nums[j + 1] = nums[j];
                } else {
                    //元素比t小或等于，则j+1的位置为t应该存在的位置，并结束循环
                    nums[j + 1] = t;
                    break;
                }
            }
        }
        return nums;
    }

}
